package a06_栈与队列;

import java.util.Deque;
import java.util.LinkedList;

//要构造一个大顶堆
//push:如果前面有比他小的，从里面去除
//pop:如果pop的元素和他顶端的一样才去除
//getMax:返回顶端元素
public class a07_滑动窗口最大值复习3 {

    public static void main(String[] args) {
        Deque<Integer> deque = new LinkedList<>();
        deque.push(1);
        deque.push(2);
        deque.push(3);
        System.out.println(deque.peekFirst());//3
        System.out.println(deque.peekLast());//1

        int[] ints = maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3);
        System.out.println();
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        //从k-1 到 nums.length-1
        int[] result = new int[nums.length - k + 1];

        //1,3,-1,-3,5,3,6,7
        //
        MyDeque4 myDeque4 = new MyDeque4();

        //先走k-1
        for (int i = 0; i < k - 1; i++) {
            myDeque4.push(nums[i]);
        }

        //然后第k布，需要计算最大值，但不吐出元素
        myDeque4.push(nums[k-1]);
        result[0] = myDeque4.getMax();

        for (int i = k; i < nums.length; i++) {
            myDeque4.pop(nums[i - k]);
            myDeque4.push(nums[i]);
            result[i - k + 1] = myDeque4.getMax();
        }

        return result;
    }
}

class MyDeque4{

    private Deque<Integer> deque;

    public MyDeque4() {
        this.deque = new LinkedList<>();
    }

    public void push(int val){
        while (!deque.isEmpty() && deque.peekFirst() < val) {
            deque.pollFirst();
        }
        deque.push(val);
    }

    public void pop(int val){
        if(!deque.isEmpty() && deque.peekLast() == val){
            deque.pollLast();
        }
    }

    public int getMax(){
        return deque.peekLast();
    }


}
